package org.lql.algo.codecrush.week004;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author: liangqinglong
 * @date: 2025-08-01 17:51
 * @description: 84. 柱状图中最大的矩形 <a href="https://leetcode.cn/problems/largest-rectangle-in-histogram/description/">...</a>
 **/
public class LargestRectangleArea {

	/**
	 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
	 * <p>
	 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
	 */
	public int largestRectangleArea(int[] heights) {
		Stack<React> stack = new Stack<>();
		heights = Arrays.copyOf(heights, heights.length + 1);
		int ans = 0;
		for (int height : heights) {
			int accumulationWidth = 0;
			while (!stack.isEmpty() && stack.peek().height > height) {
				React react = stack.pop();
				accumulationWidth += react.width;
				ans = Math.max(ans, accumulationWidth * react.height);
			}
			stack.push(new React(accumulationWidth + 1, height));
		}
		return ans;
	}

	static class React {
		int width;
		int height;

		public React(int width, int height) {
			this.width = width;
			this.height = height;
		}
	}

	public static void main(String[] args) {
		LargestRectangleArea largestRectangleArea = new LargestRectangleArea();
		System.out.println(largestRectangleArea.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3}));
	}
}
